package stack;

/**
 * 以下解法 push、pop复杂度 o(1)
 * 但是 increment 复杂度o(k)
 * 考虑用前缀和优化
 */
class CustomStack {

    private int[] stack ;
    private int top = -1;// 初始栈空  top指向当前栈顶元素的位置
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
    }

    public void push(int x) {
        if(top < stack.length - 1) {
            stack[++top] = x;
        }
    }

    public int pop() {
        return top == -1? -1 : stack[top --];
    }

    public void increment(int k, int val) {
        for(int i = 0; i < Math.min(k , top + 1); i ++) {
            stack[i] += val;
        }
    }
}

/**
 * 利用前缀和来优化  https://lucifer.ren/blog/2020/09/27/atMostK/
 *
 * 前缀和是一种重要的预处理，能大大降低查询的时间复杂度。我们可以简单理解前缀和为“数列的前 n 项的和”。
 * 本题是"数列后n位的和" 是倒着的前缀和
 * 这个概念其实很容易理解，即一个数组中，第 n 位存储的是数组前 n 个数字的和。
 * 使用空间换时间  新增一个记录增量的数组
 * pop的时候增量跟随top向低位叠加转移
 * increment的时候增加top位置val即可
 */
class CustomStack_TrieSum {

    private int[] stack ;
    private int[] inc;
    private int top = -1;// 初始栈空  top指向当前栈顶元素的位置
    public CustomStack_TrieSum(int maxSize) {
        stack = new int[maxSize];
        inc = new int[maxSize];
    }

    public void push(int x) {
        if(top < stack.length - 1) {
            stack[++top] = x;
        }
    }

    public int pop() {
        if(top == -1) return -1;
        int res = stack[top] + inc[top];
        if(top > 0) {
            inc[top - 1] += inc[top];
        }
        inc[top] = 0;// 避免increment方法再次自增的时候又加上了
        top --;
        return res;
    }

    public void increment(int k, int val) {
        int incMax = Math.min(top, k - 1);
        // 要给对应位置赋值  incMax应该指向最大位置
        if(incMax >= 0) {
            // 注意是叠加  不能直接赋值 =
            inc[incMax] += val;
        }
    }
}

private class CustomStack_20220118 {
    private int size;
    private int cur;
    private int[] nums;
    private int[] adds;
    public CustomStack(int maxSize) {
        this.size = maxSize;
        this.cur = -1;
        this.nums = new int[maxSize];
        this.adds = new int[maxSize];

    }
    
    public void push(int x) {
        if(cur == size - 1) return;
        nums[++cur] = x;
    }
    
    public int pop() {
        if(cur == -1) return -1;
        if(cur > 0) adds[cur - 1] += adds[cur];
        int res = nums[cur] + adds[cur];
        adds[cur--] = 0;
        return res;
    }
    
    public void increment(int k, int val) {
        if(cur == -1) return;
        adds[Math.min(cur,k - 1)] += val;
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack obj = new CustomStack(maxSize);
 * obj.push(x);
 * int param_2 = obj.pop();
 * obj.increment(k,val);
 */
